package com.zto.sch.advance.algorithms.book.grokking;

import com.zto.sch.advance.algorithms.Pair;
import com.zto.sch.base.util.CommonUtil;
import org.junit.Test;

import java.util.Arrays;

import static org.apache.commons.lang3.ArrayUtils.swap;

/**
 * @program: sch-diy-parent
 * @description:
 * @author: sch
 * @create: 2021-07-10 17:53
 **/
public class 选择排序 {
    /**
     * 方法1
     */
    @Test
    public void testSelectSort() {
        Integer[] beforArr = CommonUtil.getRandomArray(10);
        System.out.println("原始:" + Arrays.toString(beforArr));

        int[] afterSortArr = selectSrot(beforArr);

        System.out.println("排序后:" + Arrays.toString(afterSortArr));
    }

    /**
     * 方法2：
     * 思路：双重for循环
     * 外循环：用来找每个索引入元素
     * 内循环：用来找余下无序元素的最值
     * <p>
     * 1，第一次外层循环后找到arr[0]位置元素:拿arr[0]与后面所有元素比较
     * 2，第二次外层循环后找到arr[1]位置元素:拿arr[1]与后面所有元素比较
     * ...
     * 3，第n次外层循环后找到arr[n]位置元素
     */
    @Test
    public void testSelectSor2() {
        Integer[] arr = CommonUtil.getRandomArray(10);
        System.out.println("原始:" + Arrays.toString(arr));
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    swap(arr, i, j);
                }
            }
            System.out.println("第" + (i + 1) + "次交换后的数组:" + Arrays.toString(arr));
        }

        System.out.println("排序后:" + Arrays.toString(arr));
    }

    private void swapMethod(Integer[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 思路：
     * 1，定义一个新数据 arr
     * 2，遍历老数组一次，找到最小值放到新数据0处。并把最小值从老数组移除
     * 3，再遍历老数组一次，找到第二小值放到新数据1处，并把该值从老数组移除
     * 4，重复2~3，直接找到所有元素位置
     *
     * @param beforArr
     * @return
     */
    private int[] selectSrot(Integer[] beforArr) {
        int length = beforArr.length;
        int[] newArr = new int[length];
        for (int i = 0; i < length; i++) {
            Pair<Integer, Integer[]> pair = findMinst(beforArr);
            newArr[i] = pair.getLeft();
            beforArr = pair.getRight();
        }

        return newArr;
    }

    private Pair<Integer, Integer[]> findMinst(Integer[] beforArr) {
        int tempMin = beforArr[0];
        int tempMinIndex = 0;

        for (int i = 0; i < beforArr.length; i++) {
            if (tempMin > beforArr[i]) {
                tempMin = beforArr[i];
                tempMinIndex = i;
            }
        }
        Integer[] arr = deleteArr(beforArr, tempMinIndex);

        return new Pair<>(tempMin, arr);
    }

    private Integer[] deleteArr(Integer[] beforArr, int tempMinIndex) {
        Integer[] deletAfterArr = new Integer[beforArr.length - 1];

        int k = 0;
        for (int i = 0; i < beforArr.length; i++) {
            if (i != tempMinIndex) {
                deletAfterArr[k] = beforArr[i];
                k++;
            }
        }
        System.out.println("删除最小元素后的数组：" + Arrays.toString(deletAfterArr));

        return deletAfterArr;
    }
}
